package com.hl.algor_data_struct.sort;

/**
 * Created by yuanhailong on 2021/10/23.
 *
 * 在一个Int类型的数组中 1） 一种数出现了奇数次，其他都是偶数次，如何找到这个奇数组
                       2） 二种数出现了奇数次，其他都是偶数次，如何找到这二个奇数组

 *    ^ 异或运算：
 *          1） 不同为1 相同为0
 *          2） 0^N = N    N^N=0
 *          3)  异或运算满足交换和结合
 *     ~ 取反操作  如  二进制  10101010 取反后为01010101
 *     & 两个数都是1 则等于1 否则等于0
 *     | 两个数中只要有一个数字为1等于1，否则等于0
 */
public class FindEvenNum {

    // 1） 一种数出现了奇数次，其他都是偶数次，如何找到这个奇数组
    public static void findEven1(){
        //异或运算的交换得知
        //下面的数组用{1,1,2,2,3,3,3,3,4,4,4} 运算结果是一样的
        //又因为 N^N =0  可得出只要是偶数 异或后都会的到0
        //最终留下来的数据就是那个奇数次出现的数据
        int[] arr={1,3,3,1,3,3,2,2,4,4,4};
        int eor=0;
        for(int i=0;i<arr.length;i++){
            eor = eor ^ arr[i];
        }
        System.out.println(eor);
    }


    //2） 二种数出现了奇数次，其他都是偶数次，如何找到这二个奇数组
    public static void findEven2(){
        int[] arr={1,3,1,3,3,2,2,4,4,4};
        int eor=0;
        //这个for循坏计算完成后 eor的结果是两个奇数的异或 本例就是eor=3^4  假如最终的结果eor=a^b
        // 根据题目要求 可得知  a!=b 且  eor！=0
        //  如果 eor!=0 则表明  eor的二进制的某一位上至少有一位是1
        for(int i=0;i<arr.length;i++){
            eor = eor ^ arr[i];
        }

        int rightOne = eor & (~eor +1); //提取出最右侧的1


        int onlyOne=0;

        for(int cur:arr){
            if((cur & rightOne)  == 1){
                onlyOne ^=cur;
            }
        }

        System.out.println(onlyOne + "   "  +(onlyOne^eor));






    }




    public static void main(String[] args) {
        //findEven1();

        findEven2();
    }
}
